skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


  • Home
  • Search Results
  • Page 1 of 2

Search for: All records

Creators/Authors contains: "Luo, Ruth"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; ; (, The Electronic Journal of Combinatorics)
    Dirac proved that each $$n$$-vertex $$2$$-connected graph with minimum degree $$k$$ contains a cycle of length at least $$\min\{2k, n\}$$. We obtain analogous results for Berge cycles in hypergraphs. Recently, the authors proved an exact lower bound on the minimum degree ensuring a Berge cycle of length at least $$\min\{2k, n\}$$ in $$n$$-vertex $$r$$-uniform $$2$$-connected hypergraphs when $$k \geq r+2$$. In this paper we address the case $$k \leq r+1$$ in which the bounds have a different behavior. We prove that each $$n$$-vertex $$r$$-uniform $$2$$-connected hypergraph $$H$$ with minimum degree $$k$$ contains a Berge cycle of length at least $$\min\{2k,n,|E(H)|\}$$. If $$|E(H)|\geq n$$, this bound coincides with the bound of the Dirac's Theorem for 2-connected graphs. 
    more » « less
    Free, publicly-accessible full text available January 17, 2026
  2. ; ; (, Discrete Mathematics)
    Free, publicly-accessible full text available November 1, 2025
  3. ; ; (, Journal of Combinatorial Theory, Series B)
    Full Text Available 
  4. ; ; (, Combinatorica)
    An analog of Dirac’s Theorem for Long Cycles in 2-Connected Graphs. 
    more » « less
    Full Text Available 
  5. ; ; (, European Journal of Combinatorics)
    Full Text Available 
  6. ; (, European Journal of Combinatorics)
    Full Text Available 
  7. ; ; (, The Electronic Journal of Combinatorics)
    Let $D=(V,A)$ be a digraph. A vertex set $$K\subseteq V$$ is a quasi-kernel of $$D$$ if $$K$$ is an independent set in $$D$$ and for every vertex $$v\in V\setminus K$$, $$v$$ is at most distance 2 from $$K$$. In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. P. L. Erdős and L. A. Székely in 1976 conjectured that if every vertex of $$D$$ has a positive indegree, then $$D$$ has a quasi-kernel of size at most $|V|/2$. This conjecture is only confirmed for narrow classes of digraphs, such as semicomplete multipartite, quasi-transitive, or locally semicomplete digraphs. In this note, we state a similar conjecture for all digraphs, show that the two conjectures are equivalent, and prove that both conjectures hold for a class of digraphs containing all orientations of 4-colorable graphs (in particular, of all planar graphs). 
    more » « less
    Full Text Available 
  8. ; ; ; (, Journal of Graph Theory)
    Full Text Available 
  9. ; (, The Electronic Journal of Combinatorics)
    Let $$H$$ and $$F$$ be hypergraphs. We say $$H$$ {\em contains $$F$$ as a trace} if there exists some set $$S \subseteq V(H)$$ such that $$H|_S:=\{E\cap S: E \in E(H)\}$$ contains a subhypergraph isomorphic to $$F$$. In this paper we give an upper bound on the number of edges in a $$3$$-uniform hypergraph that does not contain $$K_{2,t}$$ as a trace when $$t$$ is large. In particular, we show that $$\lim_{t\to \infty}\lim_{n\to \infty} \frac{\mathrm{ex}(n, \mathrm{Tr}_3(K_{2,t}))}{t^{3/2}n^{3/2}} = \frac{1}{6}.$$ Moreover, we show $$\frac{1}{2} n^{3/2} + o(n^{3/2}) \leqslant \mathrm{ex}(n, \mathrm{Tr}_3(C_4)) \leqslant \frac{5}{6} n^{3/2} + o(n^{3/2})$$. 
    more » « less
    Full Text Available 
  10. ; (, The Electronic Journal of Combinatorics)
    Gyárfas proved that every coloring of the edges of $$K_n$$ with $t+1$ colors contains a monochromatic connected component of size at least $n/t$. Later, Gyárfás and Sárközy asked for which values of $$\gamma=\gamma(t)$$ does the following strengthening for almost complete graphs hold: if $$G$$ is an $$n$$-vertex graph with minimum degree at least $$(1-\gamma)n$$, then every $(t+1)$-edge coloring of $$G$$ contains a monochromatic component of size at least $n/t$. We show $$\gamma= 1/(6t^3)$$ suffices, improving a result of DeBiasio, Krueger, and Sárközy. 
    more » « less
    Full Text Available